#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include <functional>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007

class Solution
{
public:
    int n = 0;
    int m = 0;
    std::array<int, 5> move = {-1, 0, 1, 0, -1};
    std::vector<std::vector<int>> dp;

    int longestIncreasingPath(std::vector<std::vector<int>>& matrix)
    {
        n = matrix.size();
        m = matrix[0].size();
        dp.resize(n, std::vector<int>(m, -1));
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (j==2)
                {
                    std::cout << 1;
                }
                ans = std::max(ans, f(matrix, i, j));
            }
        }
        return ans;
    }

    int f(const std::vector<std::vector<int>>& matrix, int i, int j)
    {
        int x = 0;
        int y = 0;
        int res = 0;

        if (dp[i][j] != -1 ) return dp[i][j];
        for (int k = 0; k < 4; k++)
        {
            x = i + move[k];
            y = j + move[k + 1];
            if (x < 0 || y < 0 || x >= n || y >= m) continue;
            if (matrix[x][y] <= matrix[i][j]) continue;
            res = std::max(res, f(matrix, x, y));
        }
        dp[i][j] = res+1;
        return res+1;
    }
};

